home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d13 / pdsrt211.arc / PDSORT.C < prev    next >
Text File  |  1990-06-18  |  12KB  |  436 lines
  1. /*
  2.    ****************************  NOTICE!  **************************
  3.    *   Contrary to the current trend  in  MS-DOS  software  this   *
  4.    *   program,  for  whatever  it is worth,  is NOT copyrighted   *
  5.    *   (with the exception of the runtime library  from  Borland   *
  6.    *   International's  Turbo  C)!  The program,  in whole or in   *
  7.    *   part,  may be used freely in any fashion  or  environment   *
  8.    *   desired.  If  you  find this program to be useful to you,   *
  9.    *   do NOT send any contribution to the author;  in the words   *
  10.    *   of  Rick  Conn,   'Enjoy!'  However,   if  you  make  any   *
  11.    *   improvements,  I would enjoy  receiving  a  copy  of  the   *
  12.    *   modified  source.  I  can  be reached,  usually within 24   *
  13.    *   hours,  by  messages  on  any  of  the  Phoenix  systems,   *
  14.    *   particularly:                                               *
  15.    *                                                               *
  16.    *               The Tool Shop BBS       [PCBOARD]               *
  17.    *                   (602) 279-2673   1200/2400/9600 bps         *
  18.    *                   (Good luck trying!  VERY BUSY!)             *
  19.    *               Technoids Anonymous     [PCBOARD]               *
  20.    *                   (602) 899-4876   300/1200/2400 bps          *
  21.    *                                                               *
  22.    *   All can be reached through PC Pursuit.                      *
  23.    *                                                               *
  24.    *   or:                                                         *
  25.    *                on GEnie, mail address: DON-WILL               *
  26.    *                on CompuServ:           75410,543              *
  27.    *                                                               *
  28.    *   Every  effort has been made to avoid error and moderately   *
  29.    *   extensive testing has been  performed  on  this  program,   *
  30.    *   however, the author does not warrant it to be fit for any   *
  31.    *   purpose  or  to  be  free  from  error  and disclaims any   *
  32.    *   liability for actual or any other damage arising from the   *
  33.    *   use of this program.                                        *
  34.    *****************************************************************
  35. */
  36.  
  37. #include <stdlib.h>
  38. #include <stdio.h>
  39. #include <string.h>
  40. #include <alloc.h>
  41. #include <ctype.h>
  42. #include <dir.h>
  43. #include <dos.h>
  44.  
  45. #include "queue.h"
  46.  
  47. void            GetArgs (int argc, char *argv[]);
  48. void            InvalArgu (char *Msg);
  49. int             FillSortArray (void);
  50. void            Usage (void);
  51. int             isdevice (int handle);
  52.  
  53. void            Merge (void);
  54.  
  55. unsigned long   MaxMem;
  56. int             S_ArraySize;
  57. char          **SortArray;
  58. int             KeyCount = 0;
  59. int             RecLen = 0;
  60. unsigned long   DiskAdr = 0;
  61. unsigned long   NextAdr = 0;
  62. unsigned long   EndAdr;
  63. long            TotalRecs = 0;
  64. long            OutCount = 0;
  65. char            Buffer[512];
  66. FILE           *fin = NULL;
  67. FILE           *fint, *fout;
  68. unsigned long   lnno = 0;
  69. QUE_DEF        *Keys, Runs;
  70. long            BufSize;
  71. char            IntPath[65] = "";
  72.  
  73. unsigned        DeBug = 0;
  74.  
  75. struct KeyEntry {
  76.     int             Begin;
  77.     int             Len;
  78.     char            Order;
  79.     char            Case;
  80.     char            Type;
  81.     };
  82.  
  83. typedef struct RunStruct {
  84.     unsigned long   Begin;
  85.     unsigned long   Count;
  86.     }               RUN_ENT;
  87.  
  88. char            InputName[65] = "";
  89. char            OutName[65] = "";
  90. char            IntName[65] = "";
  91. long            Temp;
  92.  
  93.  void
  94. main (int argc, char *argv[]) {
  95.     extern int      comp();
  96.  
  97.     int             i, Count;
  98.     RUN_ENT        *r;
  99.     struct dfree    DiskTab;
  100.     char           *p;
  101.     char            OutDisk;
  102.     char            IntDisk;
  103.     long            DiskFree;
  104.     struct KeyEntry *t;
  105.  
  106.     fprintf(stderr, "PDSORT Version 2.1.0:  June 5, 1990\n");
  107.     if (argc < 2) Usage();
  108.     if ((Keys = malloc(sizeof(QUE_DEF))) == NULL) {
  109.         fprintf(stderr, "Insufficient memory for Key queue.\n");
  110.         exit(1);
  111.         }
  112.     InitQueue(Keys);
  113.     InitQueue(&Runs);
  114.     GetArgs(argc, argv);
  115.     if (RecLen <= 0) {
  116.         fprintf(stderr, "You must supply a record length.\n");
  117.         exit(1);
  118.         }
  119.     if (Keys->Count == 0) {
  120.         if ((t = malloc(sizeof(struct KeyEntry))) == NULL) {
  121.             fprintf(stderr, "Insufficient memory for Key entry.\n");
  122.             exit(1);
  123.             }
  124.         t->Order = 'a';
  125.         t->Case = 'm';
  126.         t->Type = 'c';
  127.         t->Begin = 0;
  128.         t->Len = RecLen;
  129.         Enque(Keys, t);
  130.         }
  131.  
  132.     if (fin != stdin) {
  133.         if ((fin = fopen(InputName, "r")) == NULL) {
  134.             fprintf(stderr, "I can't find input file: %s", InputName);
  135.             perror("");
  136.             exit(1);
  137.             }
  138.         }
  139.     if (!isdevice(fileno(fin))) {
  140.         fseek(fin, 0, SEEK_END);
  141.         EndAdr = ftell(fin);
  142.         fseek(fin, 0, SEEK_SET);
  143.         }
  144.     else EndAdr = 0;
  145.  
  146.     if (fin != stdin) {
  147.         if ((p = strchr(OutName, ':')) != NULL) OutDisk = toupper(OutName[0]);
  148.         else OutDisk = getdisk() + 1;
  149.         getdfree(OutDisk, &DiskTab);
  150.         DiskFree = (long) DiskTab.df_avail * DiskTab.df_sclus * DiskTab.df_bsec;
  151.         if (DiskFree < EndAdr) {
  152.             fprintf(stderr, "Insufficient space on output disk.\n");
  153.             exit(1);
  154.             }
  155.         if (IntPath[0] != '\0') {
  156.             if (IntPath[1] == ':') IntDisk = toupper(IntPath[0]);
  157.             else IntDisk = getdisk() + 1;
  158.             }
  159.         else {
  160.             if ((p = strrchr(OutName, '\\')) != NULL)
  161.                 strncpy(IntPath, OutName, (int) (p - OutName + 1));
  162.             else {
  163.                 IntPath[0] = OutDisk + '@';
  164.                 IntPath[1] = ':';
  165.                 IntPath[2] = '\\';
  166.                 getcurdir(OutDisk, &IntPath[3]);
  167.                 }
  168.             IntDisk = IntPath[0] - '@';
  169.             }
  170.         getdfree(IntDisk, &DiskTab);
  171.         DiskFree = (long) DiskTab.df_avail * DiskTab.df_sclus * DiskTab.df_bsec;
  172.         if (DiskFree < EndAdr) {
  173.             fprintf(stderr, "Insufficient space on intermediate disk.\n");
  174.             exit(1);
  175.             }
  176.         }
  177.  
  178.     MaxMem = coreleft();
  179.     MaxMem -= 4 * 1024L;
  180.  
  181.     S_ArraySize = (int) (MaxMem / (RecLen + 2 + sizeof(char far *) + 10));
  182.     if ((SortArray = malloc(S_ArraySize * sizeof(char far *))) == NULL) {
  183.         fprintf(stderr, "Major Error! Insufficient memory for Sort Array.\n");
  184.         exit(1);
  185.         }
  186.  
  187.     for (i = 0;
  188.          (i < S_ArraySize && coreleft() >= ((4 * 1024L) + RecLen + 2));
  189.          i++) {
  190.         if ((SortArray[i] = malloc(RecLen + 2)) == NULL) {
  191.             fprintf(stderr, "Major Error! Insufficient memory for sort item.\n");
  192.             exit(1);
  193.             }
  194.         }
  195.     S_ArraySize = i;
  196.     fprintf(stderr, "Max records per run = %d\n", S_ArraySize);
  197.  
  198.     BufSize = (coreleft() - 1024) / 2;
  199.  
  200.     Count = FillSortArray();
  201.  
  202.     TotalRecs += Count;
  203.     if (NextAdr >= EndAdr) {
  204.         fprintf(stderr, "Total records read = %ld\n", TotalRecs);
  205.         if (fin != stdin) {
  206.             fclose(fin);
  207.             if ((fout = fopen(OutName, "w")) == NULL) {
  208.                 fprintf(stderr, "I can't create output file: %s", OutName);
  209.                 perror("");
  210.                 exit(1);
  211.                 }
  212.             }
  213.         errno = 0;
  214.  
  215.         qsort(SortArray, Count, sizeof(char far *), comp);
  216.  
  217.         for (i = 0; i < Count; i++) {
  218.             fputs(SortArray[i], fout);
  219.             if (errno) {
  220.                 perror("I/O error on output file");
  221.                 exit(1);
  222.                 }
  223.             OutCount++;
  224.             }
  225.         }
  226.     else {
  227.         while (Count > 0) {
  228.             if (fint == NULL) {
  229.                 strcpy(IntName, IntPath);
  230.                 strcat(IntName, "\\SORT.$$$");
  231.                 if ((fint = fopen(IntName, "w")) == NULL) {
  232.                     fprintf(stderr, "I can't create sort intermediate file: %s", IntName);
  233.                     perror("");
  234.                     exit(1);
  235.                     }
  236.                 errno = 0;
  237.                 }
  238.             DiskAdr = ftell(fint);
  239.  
  240.             qsort(SortArray, Count, sizeof(char far *), comp);
  241.  
  242.             if ((r = malloc(sizeof(RUN_ENT))) == NULL) {
  243.                 fprintf(stderr, "Insufficient memory for Run Entry!\n");
  244.                 exit(1);
  245.                 }
  246.             r->Begin = DiskAdr;
  247.             r->Count = Count;
  248.             Enque(&Runs, r);
  249.  
  250.             for (i = 0; i < Count; i++) {
  251.                 fputs(SortArray[i], fint);
  252.                 if (errno) {
  253.                     perror("I/O error on intermediate file");
  254.                     exit(1);
  255.                     }
  256.                 }
  257.             Count = FillSortArray();
  258.             TotalRecs += Count;
  259.             }
  260.         fprintf(stderr, "Total records read = %ld\n", TotalRecs);
  261.         if (fin != stdin) {
  262.             fclose(fin);
  263.             if ((fout = fopen(OutName, "w")) == NULL) {
  264.                 fprintf(stderr, "I can't create output file: %s", OutName);
  265.                 perror("");
  266.                 exit(1);
  267.                 }
  268.             }
  269.         errno = 0;
  270.         qsort(SortArray, Count, sizeof(char far *), comp);
  271.         for (i = 0; i < Count; i++) {
  272.             fputs(SortArray[i], fout);
  273.             if (errno) {
  274.                 perror("I/O error on output file");
  275.                 exit(1);
  276.                 }
  277.             }
  278.         Merge();
  279.         }
  280.     unlink(IntName);
  281.     fprintf(stderr, "Total records written = %ld\n", OutCount);
  282.     }
  283.  
  284.  
  285.  void
  286. GetArgs (int argc, char *argv[]) {
  287.     int             i;
  288.     char           *p1, *p2;
  289.     struct KeyEntry *t;
  290.  
  291.     for (i = 1; i < argc; ++i) {
  292.         if (argv[i][0] != '-') continue;
  293.         if (!strcmp(argv[i], "-")) {
  294.             fin = stdin;
  295.             fout = stdout;
  296.             continue;
  297.             }
  298.         switch (tolower(argv[i][1])) {
  299.             case 't':
  300.                 strcpy(IntPath, &argv[i][2]);
  301.                 break;
  302.             default:
  303.                 fprintf(stderr, "Invalid option: %s\n", argv[i]);
  304.                 Usage();
  305.             }
  306.         }
  307.  
  308.     for (i = 1; i < argc; ++i) {
  309.         if (argv[i][0] == '-') continue;
  310.         if (fin == NULL) {
  311.             if (InputName[0] == '\0') {
  312.                 strcpy(InputName, argv[i]);
  313.                 continue;
  314.                 }
  315.             else if (OutName[0] == '\0') {
  316.                 strcpy(OutName, argv[i]);
  317.                 continue;
  318.                 }
  319.             }
  320.         p1 = argv[i];
  321.         if (!isdigit(p1[0])) InvalArgu(argv[i]);
  322.         if ( (RecLen == 0) && (strspn(p1, "0123456789") == strlen(p1)) ) {
  323.             RecLen = atoi(argv[i]);
  324.             continue;
  325.             }
  326.         p2 = &p1[strspn(p1, "0123456789")];
  327.         if ((t = malloc(sizeof(struct KeyEntry))) == NULL) {
  328.             fprintf(stderr, "Insufficient memory for Key entry.\n");
  329.             exit(1);
  330.             }
  331.         t->Order = 'a';
  332.         t->Case = 'm';
  333.         t->Type = 'c';
  334.         t->Begin = atoi(p1) - 1;
  335.         if (*p2 == ':') t->Len = atoi(++p2);
  336.         else if (*p2 == '-') t->Len = atoi(++p2) - t->Begin;
  337.         else InvalArgu(argv[i]);
  338.         p1 = p2;
  339.         p2 = &p1[strspn(p1, "0123456789")];
  340.         if (*p2 == ':') {
  341.             p1 = ++p2;
  342.             while (*p1 != '\0') {
  343.                 switch (tolower(*p1++)) {
  344.                     case 'd':
  345.                         t->Order = 'd';
  346.                         break;
  347.                     case 'a':
  348.                         t->Order = 'a';
  349.                         break;
  350.                     case 'i':
  351.                         t->Case = 'i';
  352.                         break;
  353.                     case 'm':
  354.                         t->Case = 'm';
  355.                         break;
  356.                     case 'c':
  357.                         t->Type = 'c';
  358.                         break;
  359.                     default:
  360.                         InvalArgu(argv[i]);
  361.                     }
  362.                 }
  363.             }
  364.         else if (*p2 != '\0') InvalArgu(argv[i]);
  365.         Enque(Keys, t);
  366.         }
  367.     }
  368.  
  369.  void
  370. InvalArgu (char *Msg) {
  371.     fprintf(stderr, "Invalid argument: %s.\n", Msg);
  372.     Usage();
  373.     }
  374.  
  375.  
  376.  int
  377. FillSortArray (void) {
  378.     int             i;
  379.  
  380.     for (i = 0; i < S_ArraySize; i++) {
  381.         if (fgets(Buffer, RecLen + 1, fin) == NULL) return (i);
  382.         if (errno) {
  383.             perror("I/O error on input file");
  384.             exit(1);
  385.             }
  386.         NextAdr = ftell(fin);
  387.         lnno++;
  388.         if ((strlen(Buffer) == RecLen) && (Buffer[strlen(Buffer) - 1] != '\n')) {
  389.             fprintf(stderr, "Record #%d exceeds maximum length %d\n",
  390.                     lnno, RecLen);
  391.             exit(1);
  392.             }
  393.         strcpy(SortArray[i], Buffer);
  394.         }
  395.     return (i);
  396.     }
  397.  
  398.  
  399.  int
  400. comp (const void *aa, const void *bb) {
  401.     char          **a, **b;
  402.     char            HoldA, HoldB;
  403.     int             End, Result;
  404.     QUE_ENTRY      *t;
  405.     struct KeyEntry *v;
  406.  
  407.     a = (char **) aa;
  408.     b = (char **) bb;
  409.     if (*a == *b) return (0);
  410.     if (*a == NULL) return (1);
  411.     if (*b == NULL) return (-1);
  412.     for (Result = 0, t = Keys->Head; (t != NULL) && (Result == 0); t = t->Next) {
  413.         v = t->Body;
  414.         End = v->Begin + v->Len;
  415.         HoldA = (*a)[End];
  416.         (*a)[End] = '\0';
  417.         HoldB = (*b)[End];
  418.         (*b)[End] = '\0';
  419.         Result = (v->Order == 'a') ?
  420.             (v->Case == 'i') ? stricmp(&(*a)[v->Begin], &(*b)[v->Begin])
  421.             : strcmp(&(*a)[v->Begin], &(*b)[v->Begin])
  422.             : (v->Case == 'i') ? stricmp(&(*b)[v->Begin], &(*a)[v->Begin])
  423.             : strcmp(&(*b)[v->Begin], &(*a)[v->Begin]);
  424.         (*a)[End] = HoldA;
  425.         (*b)[End] = HoldB;
  426.         }
  427.     return (Result);
  428.     }
  429.  
  430.  
  431.  void
  432. Usage (void) {
  433.     fprintf(stderr, "USAGE: pdsort input_file output_file rec_len\n");
  434.     exit(1);
  435.     }
  436.